#include "linearList.h"

//构造函数和析构函数
sequenceList::sequenceList(const int& maxCapcity, const int& curNumberOfItem, float myList[]){
    this->maxCapcity = maxCapcity;
    this->curNumberOfItem = curNumberOfItem;
    this->myList = new float[maxCapcity];
    for(int i = 0;i < curNumberOfItem;i++){
        this->myList[i] = myList[i];
    }
}

sequenceList::~sequenceList(){

}

//添加表尾元素
bool sequenceList::addItem(const float& val){
    if(this->curNumberOfItem == this->maxCapcity) return false;
    this->myList[curNumberOfItem] = val;
    curNumberOfItem++;
    return true;
}

//插入元素
bool sequenceList::insertItem(const int& index,const float& val){
    if(index < 0 || index > curNumberOfItem) return false;
    if(curNumberOfItem == maxCapcity) return false;
    for(int i = curNumberOfItem;i > index;i--){
        this->myList[i]=this->myList[i-1];
    }
    this->myList[index] = val;
    this->curNumberOfItem++;
    return true;
}

//删除元素
int sequenceList::deleteItem(const float& val){
    int tag = -1;
    for(int i = 0;i < curNumberOfItem;i++){
        if(this->myList[i] == val){
            for(int j = i;j < curNumberOfItem;j++){
                this->myList[j] = this->myList[j+1];
            }
            tag = i;
            this->curNumberOfItem--;
            break;      //删除第一个找到的需跳出循环
        }
    }
    return tag;
}

//按序号查找元素
bool sequenceList::locate(const int& index, float& val){
    if(index < 0 || index >= curNumberOfItem) return false;
    val = this->myList[index];
    return true;
}

//按值查找元素
int sequenceList::locate(const float& val){
    for(int i = 0;i < curNumberOfItem;i++){
        if(val == this->myList[i]){
            return i;
        }
    }
    return -1;
}

//倒序排列元素
void sequenceList::reverse(){
    for(int i = 0;i < (curNumberOfItem/2);i++){
        float temp;
        temp = this->myList[i];
        this->myList[i] = this->myList[curNumberOfItem-i-1];
        this->myList[curNumberOfItem-i-1] = temp;
    }
}

//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}

//------------------------------------------------------------

//初始化结点
listNode::listNode(float nodeData, listNode* succ){
    this->data = nodeData;
    this->next = succ;

}

listNode::~listNode(){

}

// 默认构造函数
linkList::linkList() {
    firstNode = NULL;
    curNode = NULL;
    lastNode = NULL;
    listSize = 0;
}

//初始化链表
linkList::linkList(const int& listsize, float data[]){
    firstNode = new listNode();
    curNode = firstNode;
    lastNode = firstNode;
    this->listSize = listsize;
    for(int i = 0;i < listSize;i++){
        listNode *newNode = new listNode(data[i],NULL);
        lastNode->next = newNode;
        lastNode = newNode;
    }
    curNode = firstNode->next;
}

//销毁链表
linkList::~linkList(){
    listNode * tempNode = firstNode;
    while(tempNode != NULL){
        listNode * nextNode = tempNode->next;
        delete tempNode;
        tempNode = nextNode;
    }
    this->listSize = 0;
}


//按值头插
bool linkList::headInsertItem(const float& val){
    listNode * newNode = new listNode(val,NULL);
    if(newNode == NULL){
        return false;
    }
    newNode->next = firstNode->next;
    firstNode->next = newNode;   
    if(curNode == firstNode){
        curNode = newNode;
    }
    this->listSize++;
    return true;
}


//按值尾插
bool linkList::tailInsertItem(const float& val){
    listNode *newNode = new listNode(val,NULL);
    if(newNode == NULL){
        return false;
    }
    lastNode->next = newNode;
    if(curNode == lastNode){
        curNode = newNode;
    }
    lastNode = newNode;
    this->listSize++;
    return true;
}

//插入特定位置
int linkList::insertItem(const int& index,const float& val){
    if(index < 0 || index > listSize){
        return -1;
    }
    listNode * cur_Node = firstNode;
    for(int i = 0;i < index;i++){
        cur_Node = cur_Node->next;
    }
    listNode * newNode = new listNode(val,NULL);
    newNode->next = cur_Node->next;
    cur_Node->next = newNode;
    if(cur_Node == lastNode){      //最后一个节点插入
        lastNode = newNode;
    }
    this->listSize++;
    return 0;
}

//按值删除
int linkList::deleteItem(const float& val){
    int pos = -1;
    listNode * cur_Node = firstNode->next;
    listNode * bef_Node = firstNode;
    while(cur_Node != NULL){
        pos++;
        if(cur_Node->data == val){
            bef_Node->next = cur_Node->next;
            if(pos == this->listSize - 1){     //删除最后一个节点
                lastNode = bef_Node;
            }
            delete cur_Node;
            this->listSize--;
            return pos;
        }
        cur_Node = cur_Node->next;
        bef_Node = bef_Node->next;
    }
    return -1; 
}

//按序号查找
bool linkList::locate(const int& index, float& val){
    if(index < 0 || index >= listSize){
        return false;
    }
    listNode * cur_Node = firstNode->next;
    for(int i = 0;i < index;i++){
        cur_Node = cur_Node->next;
    }
    val = cur_Node->data;
    return true;
}

//按值查找
int linkList::locate(const float& val){
    int pos = -1;
    listNode * cur_Node = firstNode->next;
    while(cur_Node != NULL){
        pos++;
        if(cur_Node->data == val){
            return pos;
        }
        cur_Node = cur_Node->next;
    }
    return -1;
}

//递增排序
void linkList::ascendingOrder(){
    listNode * cur_Node = firstNode->next;
    for(int i = 0;i < this->listSize;i++){
        for(int j = 0;j < this->listSize - i - 1;j++){
            if(cur_Node->data > cur_Node->next->data){
                float temp;
                temp = cur_Node->data;
                cur_Node->data = cur_Node->next->data;
                cur_Node->next->data = temp;
            }
            cur_Node = cur_Node->next;
        }
        cur_Node = firstNode->next;
    }
} 

//倒序排列
void linkList::reverse(){
    listNode * cur_Node = firstNode->next;
    listNode * bef_Node = NULL;
    while(cur_Node != NULL){
        listNode * next_Node = cur_Node->next;
        cur_Node->next = bef_Node;
        bef_Node = cur_Node;
        cur_Node = next_Node;
    }
    lastNode = firstNode->next;
    firstNode->next = bef_Node;
    curNode = bef_Node;
}

//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}

//ADD:为类外函数提供类里私有成员的接口
int linkList::length(){
    return listSize;
}

//合并递减排序=递增排序＋逆序
void merge(linkList& A, linkList& B){
    for(int i = 0;i < B.length();i++){
        float value;
        B.locate(i,value);             //将B中元素插入A中
        A.headInsertItem(value);
    }
    A.ascendingOrder();
    A.reverse();
}